- Title
- Probabilistic lower bounds on maximal determinants of binary matrices
- Creator
- Brent, Richard P.; Osborn, Judy-Anne H.; Smith, Warren D.
- Relation
- ARC.DP140101417
- Relation
- Australasian Journal of Combinatorics Vol. 66, Issue 3, p. 350-364
- Relation
- https://ajc.maths.uq.edu.au/?page=get_volumes&volume=66
- Publisher
- Centre for Discrete Mathematics & Computing
- Resource Type
- journal article
- Date
- 2016
- Description
- Let D(n) be the maximal determinant for n × n {±1}-matrices, and R(n) = D(n)/nn/2 be the ratio of D(n) to the Hadamard upper bound. Using the probabilistic method, we prove new lower bounds on D(n) and R(n) in terms of d = n - h, where h is the order of a Hadamard matrix and h is maximal subject to h ≤ n. For example, [forumal cannot be replicated]. By a recent result of Livinskyi, d²/h1/2 → 0 as n → 8, so the second bound is close to (πe/2)-d/2 for large n. Previous lower bounds tended to zero as n → ∞ with d fixed, except in the cases d ∈ {0, 1}. For d ≥ 2, our bounds are better for all sufficiently large n. If the Hadamard conjecture is true, then d ≤ 3, so the first bound above shows that R(n) is bounded below by a positive constant (πe/2)-3/2 > 0.1133.
- Subject
- mathmatics; binary matrices; lower bounds
- Identifier
- http://hdl.handle.net/1959.13/1331882
- Identifier
- uon:26737
- Identifier
- ISSN:1034-4942
- Language
- eng
- Full Text
- Reviewed
- Hits: 1790
- Visitors: 1894
- Downloads: 146
Thumbnail | File | Description | Size | Format | |||
---|---|---|---|---|---|---|---|
View Details Download | ATTACHMENT02 | Publisher version (open access) | 176 KB | Adobe Acrobat PDF | View Details Download |